package LeetCode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:59
 */
public class LeetCode32 {

    public static void main(String[] args) {
        System.out.println(new LeetCode32().longestValidParentheses(")()())"));
    }



    /*常规暴力解法*/
//    public int longestValidParentheses(String s) {
//        int maxlen = 0;
//        for (int i = 0; i < s.length(); i++){
//            for (int j = i + 2; j <= s.length(); j+=2){
//                if (isValid(s.substring(i,j))){
//                    maxlen = Math.max(maxlen,j - i);
//                }
//            }
//        }
//        return maxlen;
//    }
//
//    public boolean isValid(String s){
//        Stack<Character> stack = new Stack<>();
//        for (int i = 0; i < s.length(); i++){
//            if (s.charAt(i) == '('){
//                stack.push('(');
//            }else if (!stack.empty() && stack.peek() == ')'){
//                stack.pop();
//            }else {
//                return false;
//            }
//        }
//        return stack.isEmpty();//有剩下的就是不符合的
//    }

    //动态规划
//    public int longestValidParentheses(String s) {
//        int maxans = 0;
//        int dp[] = new int[s.length()];
//        for (int i = 1; i < s.length(); i++){
//            if (s.charAt(i) == ')'){
//                if (s.charAt(i - 1) == '('){
//                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
//                }else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
//                    dp[i] = dp[i - 1]+((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
//                }
//                maxans = Math.max(maxans,dp[i]);
//            }
//        }
//        return maxans;
//    }


        //栈模式
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == '('){
                stack.push(i);
            }else {
                stack.pop();
                if (stack.empty()){
                    stack.push(i);
                }else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}
